//https://www.bilibili.com/video/BV1d54y1f7B3/?spm_id_from=333.337.search-card.all.click&vd_source=d6fe65f095f01f05591e89d810720ccc
// 2024-10-18


public class P008_链表反转_递归法 {

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        System.out.println(fun(node1));
    }

    private static Node fun(Node node1) {
        if (node1.next == null) return node1;//如果只有一个节点就直接返回

        Node new_node = fun(node1.next); // 将后续节点反转

        Node p = new_node;
        while (p.next != null) p = p.next;//找到后续链表的尾结点

        node1.next = null;//挂载第一个节点
        p.next = node1;

        return new_node;
    }

    static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}
